The invention relates generally to the field of processor scheduling, and, more specifically, to the field of scheduling the execution of real-time programs and non-real-time programs.
Multitasking operating systems allow a number of different programs to execute xe2x80x9csimultaneouslyxe2x80x9d on a single processor. Such multitasking operating systems do so by rapidly switching the processor between the execution of multiple programs.
A single program, also known as a xe2x80x9cprocess,xe2x80x9d may have one or more threads. The word xe2x80x9cthreadxe2x80x9d as used herein means the finest scheduleable unit of execution. A thread is typically represented by a data structure called an execution context, which contains state information about the execution of the thread, such as register and stack contents. When the operating system suspends a thread in favor of the execution of another thread, it copies the information from the registers and stack to the thread""s execution context. When the operating system subsequently reselects the thread for execution after suspending another thread, it copies the information in the thread""s execution context back to the actual registers and stack. In this way, the thread continues executing with the same register and stack contents as when it was suspended. One or more threads often belong to a process, which corresponds to a body of code and which may own certain single-process resources, such as blocks of memory. While processes and programs can be viewed as roughly equivalent, in some cases, multiple processes may be said to constitute a program, and in other cases, a process may include several programs.
The process of determining which threads to execute at which times is generally termed xe2x80x9cschedulingxe2x80x9d a computer system""s CPU. The way in which scheduling is performed can significantly impact a user""s perception of whether individual threads are performing adequately. Modem multimedia applications, for example, often require substantial processor time, and appear to proceed slowly or in a jerky fashion if they do not receive the required processor time.
Real-time programs are programs that have an understanding of their execution performance needs and timeliness requirements, and can interact with a real-time interface of the operating system to make those execution performance needs and timeliness requirements known to the operating system, such as multimedia applications and industrial applications. Real-time programs can each have a number of threads of execution, grouped under one or more xe2x80x9cactivities,xe2x80x9d or aspects of the real-time program whose overall execution performance needs differ. Each activity may submit a processor reservation specifying the amount of processor time that its threads collectively need on an ongoing basis. Each thread may itself submit time constraints specifying that it needs a certain amount of processor time by a certain deadline. Reservations and time constraints are known collectively as xe2x80x9cexecution timing requests.xe2x80x9d
Certain conventional schedulers handle reservations and time constraints by maintaining the information relating to the reservations and time constraints for use in identifying the next thread to execute on an ad hoc basis each time the processor becomes available for reassignment to a new thread. This conventional xe2x80x9cad hocxe2x80x9d approach to scheduling has several disadvantages. First, completely reevaluating the relative urgencies of all of the existing threads each time the processor becomes available for reassignment often consumes substantial execution time, which makes this execution time unavailable to the real-time programs. Additionally, the approach cannot guarantee at the time a reservation or time constraint is submitted that the reservation or time constraint will be honored. The ad hoc approach can also cause unnecessarily frequent thread switches, thereby reducing the efficiency gains resulting from caching information relating to the executing thread. Further, reservations, while honored for specific periods of time under the ad hoc approach, are not executed with the regularity necessary to honor the reservations over every window of time.
The present invention provides predictable scheduling of real-time programs and non-real-time programs using a repeating precomputed schedule. In accordance with the invention, a thread scheduling software facility (xe2x80x9cthe schedulerxe2x80x9d) overcomes the shortcomings of the conventional ad hoc approach to scheduling by utilizing a precomputed schedule that specifies the future execution of activities and threads having outstanding time constraints, which significantly reduces the processing required to (A) identify the next thread to execute when the processor becomes available and (B) determine the amount of time for which to execute the identified thread. As a result, the process of identifying the next thread to execute and determining the amount of time for which to execute the identified thread can be performed in a bounded amount of time that is independent of the number of threads and activities being scheduled. The precomputed schedule allows the scheduler to assess the feasibility of reservations and time constraints when they are submitted, and immediately refuse any nonfeasible reservations and time constraints. The precomputed schedule also allows the scheduler to guarantee that reservations will be honored with regularity. The precomputed schedule further allows the scheduler to maximize the length of individual intervals assigned to each thread, thereby allowing each thread to make more efficient use of caches. The scheduler further enables blocked activities to receive extra processing time when they are unblocked. The scheduler further effectively schedules the simultaneous execution of real-time and non-real-time programs on the same processor. The scheduler further is able to effectively schedule non-real-time programs in the complete absence of real-time programs, reservations, and constraints.
The precomputed schedule is preferably represented as a directed acyclic graph of nodes, each node corresponding to an execution interval of a specified length, that is incrementally traversed to determine which activity to execute next. (As discussed herein, xe2x80x9cexecuting an activityxe2x80x9d means executing one or more threads belonging to the activity.) Each node may either be dedicated to an activity, such that its interval is used to execute that activity, or designated as a xe2x80x9cfree node,xe2x80x9d whose interval may be used to execute any activity. A complete traversal of the graph is made by traversing, in turn, each path from a root node to one of a group of leaf nodes. The sum of the lengths of the intervals of the nodes in each such path is equal. The number of paths that pass through each node determine the frequency with which its interval recurs while traversing the graph.
The scheduler incorporates reservations in the scheduling graph by dedicating one or more nodes of the graph to the activity submitting the reservation. Nodes are selected that are on enough paths to be executed frequently enough to satisfy the reservation, and whose intervals are long enough to satisfy the reservation. When the scheduler traverses to a node dedicated to the activity, the scheduler executes one or more threads of that activity. The scheduler incorporates time constraints in the scheduling graph by allocating to the time constraints specific traversals through nodes of the graph that are either dedicated to the activity of the thread submitting the time constraint or that are free nodes. When the scheduler performs the allocated traversals through these nodes, the thread submitting the time constraint is executed.